# 最后一块石头的重量II(好题)
# leetcode第416题: https://leetcode.cn/problems/last-stone-weight-ii/description/
# 背包问题: https://www.bilibili.com/video/BV14M411C7oV
# Date: 2025/3/26
from leetcode import test_function as tf


def lastStoneWeightII(stones: list[int]) -> int:
    """
    将 [1,41,41,81]分为两组, 并且让两组的和尽量接近:
    arr1 = [81, 1] 和 arr2 = [41, 41]
    从两组选出重量接近的碰撞就可得到
    得到[40, 40]
    再次碰撞得到0, 也就是最小的石头重量
    所以本题和lc416相似, 即求
    res = sum(arr1) - sum(arr2)
    """
    s = sum(stones)
    w = s // 2
    dp = [0] * (w + 1)

    for stone in stones:
        for j in range(w, stone - 1, -1):
            dp[j] = max(dp[j], dp[j - stone] + stone)

    return s - dp[w] - dp[w]


if __name__ == '__main__':
    inp = [{"stones": [2, 7, 4, 1, 8, 1]}, {"stones": [31, 26, 33, 21, 40]}, ]
    out = [1, 5, ]
    tf(lastStoneWeightII, inp, out)
